package leetcode.code0316;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	class Node {
		char c;
		int index;
		Node next;
		Node pre;

		public Node() {

		}

		public Node(char c, int index) {
			this.c = c;
			this.index = index;
		}

	}

	public String removeDuplicateLetters(String s) {
		char[] sa = s.toCharArray();
		Node[] dic = new Node[26];
		Node root = new Node();
		Node p = root;
		for (char cur : sa) {
			int curIndex = cur - 'a';
			if (dic[curIndex] == null) {
				dic[curIndex] = new Node(cur, curIndex);
				p.next = dic[curIndex];
				dic[curIndex].pre = p;
				p = p.next;
			} else {
				Node next = dic[curIndex].next;
				if (next == null) {
					continue;
				}
				if (this.has(next, curIndex)) {
					Node pre = dic[curIndex].pre;
					pre.next = next;
					next.pre = pre;
					dic[curIndex] = new Node(cur, curIndex);
					p.next = dic[curIndex];
					dic[curIndex].pre = p;
					p = p.next;
				}
			}
		}
		StringBuffer ans = new StringBuffer();
		while (root.next != null) {
			root = root.next;
			ans.append(root.c);
		}
		return ans.toString();
	}

	private boolean has(Node node, int val) {
		while (node != null) {
			if (node.index < val) {
				return true;
			}
			node = node.next;
		}
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare("abc", this.removeDuplicateLetters("bcabc"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare("acdb", this.removeDuplicateLetters("cbacdcbc"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
